#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100
typedef enum { FALSE, TRUE } Boolean;
typedef struct {
    char vertex[MaxVertexNum];
    int edge[MaxVertexNum][MaxVertexNum];
} MGraph;
int locate_vertex(MGraph* G, char vertex_name) {
    int i;
    for (i = 0; i < 8; i++)
        if (G->vertex[i] == vertex_name)
            return i;
    return -1;  
}

void create_graph(MGraph** G_pp, char* graph_data_filename)
{
    FILE* fp;
    size_t len = 0;
    size_t read;
    int num_nodes, num_edges;
    fp = fopen(graph_data_filename, "r");
    if (fp == NULL)
        exit(EXIT_FAILURE);
    fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
    printf("节点数为:%d\n边数为:%d\n", num_nodes, num_edges);
    int j, h;
    (*G_pp) = (MGraph*)malloc(sizeof(MGraph));
    MGraph* gpp = *G_pp;
    for (j = 0; j < num_nodes; j++) {
        gpp->vertex[j] = fgetc(fp);
        fgetc(fp);
        printf("%c ", gpp->vertex[j]);
    }
    printf("\n");
    for (j = 0; j < num_nodes; j++) {
        for (h = 0; h < num_nodes; h++) {
            gpp->edge[j][h] = 0;
        }
    }
    char v1, v2;
    for (int k = 0; k < num_edges; k++) {
        v1 = fgetc(fp);
        printf("%c", v1);
        fgetc(fp);
        v2 = fgetc(fp);
        fgetc(fp);
        printf("%c\n", v2);
        for (j = 0; j < num_nodes; j++) {
            for (h = 0; h < num_nodes; h++) {
                if (gpp->vertex[h] == v2 && gpp->vertex[j] == v1) {
                    gpp->edge[j][h] = 1;
                    gpp->edge[h][j] = 1;
                }
            }
        }
    }
    printf("邻接矩阵如下：\n");
    for (j = 0; j < num_edges; j++) {
        for (h = 0; h < num_edges; h++) {
            printf("%d\t", gpp->edge[j][h]);
        }
        printf("\n");
    }
    fclose(fp);
}
void dfs(MGraph* G, int i, Boolean visited[], char* result_sequence, int* visited_order)
{
    int j;
    result_sequence[*visited_order] = G->vertex[i];
    (*visited_order)++;
    visited[i] = TRUE;
    for (j = 0; j < 8; j++) {
        if (G->edge[i][j] == 1 && !visited[j]) {
            dfs(G, j, visited, result_sequence, visited_order);
        }
    }

}
void bfs(MGraph* G, int k, Boolean visited[], char* visited_sequence) {
    int i, j = 0, r = 0, f = 0;
    char dl[MaxVertexNum];
    for (i = 0; i < MaxVertexNum; i++) {
        visited[i] = FALSE;
        visited_sequence[i] = 0;
        dl[i] = 0;
    }
    dl[r] = G->vertex[k];
    visited[k] = TRUE;
    while (dl[r] != 0) {
        for (i = 0; i < 8; i++) {
            if (G->edge[k][i] == 1 && visited[i] == FALSE) {
                f++;
                visited[i] = TRUE;
                dl[f] = G->vertex[i];
            }
        }
        visited_sequence[j] = dl[r];
        r++;
        k = locate_vertex(G, dl[r]);
        j++;
    }
}
void main() {
    int i;
    MGraph* G;
    Boolean visited[MaxVertexNum];

    for (i = 0; i < MaxVertexNum; i++) {
        visited[i] = FALSE;
    }
    create_graph(&G, "graph_data.txt");
    char dfs_sequence[MaxVertexNum] = { '\0' };
    int visited_order = 0;
    dfs(G, 0, visited, dfs_sequence, &visited_order);
    printf("Print Graph DFS: ");
    printf("%s\n", dfs_sequence);
    printf("\n");
    for (i = 0; i < MaxVertexNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence[MaxVertexNum] = { '\0' };
    bfs(G, 0, visited, bfs_sequence);
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence);
    char bfs_sequence2[MaxVertexNum] = { '\0' };
    bfs(G, 3, visited, bfs_sequence2);
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence2);
}